A programmable logic device (PLD) represented by a field-programmable gate array (FPGA) is a semiconductor integrated circuit which can make a change in a circuit configuration after chip fabrication. An island-style PLD includes a two-dimensional repetitive structure of computational units. A computational unit comprises programmable wiring resources and programmable logic resources.
The programmable wiring resources include a programmable crossbar which comprises a group of conductive lines, another group of conductive lines which intersect perpendicularly with the former group of conductive lines, switches which change the interconnected relation between the former group of conductive lines and the latter group of conductive lines, and a memory which records the interconnected relation. The programmable crossbar may be called a “Programmable Interconnect” or a “Programmable Switch Matrix.”
There is known a technology which constitutes a programmable crossbar from a group of conductive lines, another group of conductive lines which intersect perpendicularly with the former group of conductive lines, a group of resistance change elements at respective intersections where the former group of conductive lines intersect perpendicularly with the latter group of conductive lines. Any resistance change element is, for example, a nonvolatile resistance change element having two terminals, and an application of a predetermined voltage across the terminals causes the element to change its state between a low-resistance state and a high-resistance state. A programmable crossbar which uses two-terminal nonvolatile resistance change elements is small in area and high in routability. Therefore, the introduction of a programmable crossbar which uses two-terminal nonvolatile resistance change elements allows a PLD to have increased logic density.
There is a demand for a fault-tolerant technique which is applicable to a programmable crossbar using two-terminal nonvolatile resistance change elements. The fault-tolerant technique is a technique of avoiding an adverse effect and causing a system to normally function as a whole even if one or some of the resistance change elements may be defective. The fault-tolerant technique will be implemented by applying a certain redundancy, that is, by adding an area overhead. In order to allow any PLD to have an increased logic density, the fault-tolerant technique with few area overheads is searched for.